package org.suanfaTranning.ST200_Chatpter1_LineTable_HashTable_String.array;

import java.util.HashSet;

/**
 * @Auther: qingle
 * @Date: 2024/9/11-14:47
 * @Description: 删除排序数组的重复项
 *
 *给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出
 * 现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原
 * 地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 * 给定数组 nums = [1, 1, 2];
 * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2
 * 你不需要考虑数组中超出新长度后面的元素。
 * 给定数组 nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
 * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4
 * 你不需要考虑数组中超出新长度后面的元素。
 *
 * @version: 1.0
 */
public class doublePointer {

	// 暴力解法 O(n2) O(1)
	public int removeDuplicates(int[] nums) {
		int length = nums.length;// 数组长度

		for (int i = 0; i < length - 1; i++) {
			if (nums[i] != nums[i+1]){
				i++;
			} else {
				// 相同，所有元素后移一位
				for (int j = i + 1; j < length - 1; j++) {
					nums[j] = nums[j + 1];
				}
				// 没遇到重复元素，数组长度减一
				length--;
			}
		}
		return length;
	}

	// 双指针解法 O(n) O(1)，将带移动的数据一次性移动到目标位置
	/**
	 * • 比较相等：目标位不变，待移动位加1
	 * • 比较不等：目标位加1，待移动元素赋值到目标位；待移动位加1
	 *
	 * 地删除排序数组中的重复元素，并且返回新数组的长度。代码使用了双指针技术，其中一个指针（target）用于跟踪不重复元素应该放置的位置，另一个指针（i）用于遍历数组。下面是代码的详细解释：
	 *
	 * 首先，定义一个变量 length 来存储数组 nums 的长度。
	 *
	 * 初始化一个指针 target 为 0，这个指针指向数组中下一个不重复元素应该存放的位置。
	 *
	 * 遍历数组，从索引 1 开始，直到数组的最后一个元素（索引为 length - 1）。这里循环的条件是 i < length，确保遍历数组中的所有元素。
	 *
	 * 在每次迭代中，比较 target 指针所在位置的元素 nums[target] 与当前元素 nums[i]：
	 *
	 * 如果这两个元素不相等（即 nums[target] != nums[i]），说明 nums[i] 是一个不重复的元素，需要保留。
	 * 在保留 nums[i] 之前，先将 target 指针向前移动一位（target++），因为我们知道 target 指针所在位置的元素已经是一个不重复的元素。
	 * 然后，如果 target 指针的位置不等于当前元素的索引（即 ++target != i），将 nums[i] 的值复制到 nums[target]，这样就把当前元素移动到了 target 指针的位置。
	 * 如果 target 指针的位置已经等于当前元素的索引，说明不需要移动，直接保留即可。
	 * 循环结束后，target 指针的位置加 1 就是新数组的长度，因为 target 指向的是最后一个不重复元素的下一个位置。
	 *
	 * 函数最后返回 target + 1 作为新数组的长度。
	 *
	 * 这段代码的时间复杂度是 O(n)，因为每个元素最多被访问一次。空间复杂度是 O(1)，因为我们只使用了有限的额外空间（target 和 length 变量）。
	 * @param nums
	 * @return
	 */
	public int removeDuplicates1(int[] nums) {
		int length = nums.length;// 数组长度

		// 1.定义两个指针分比为指向待移动元素位置和目标位
		int target = 0;
		for (int i = 1; i < length; i++) {
			if (nums[target] != nums[i]) {
				if(++target != i) {
					nums[target] = nums[i];
				}
			}
		}
		return target + 1;
	}

	public static void main(String[] args) {

		int[] ints = {1, 1, 2};
		doublePointer doublePointer = new doublePointer();
		int result = doublePointer.removeDuplicates(ints);
		int result1 = doublePointer.removeDuplicates1(ints);
		System.out.println(result);
		System.out.println(result1);
	}
}
